void dijkstra()
{
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
	for(int i=1;i<=n;++i)dis[i]=0x7fffffff;
	dis[S]=0;
	q.push(make_pair(0,S));
	while(!q.empty())
	{
		int u=q.top().sec;q.pop();
		for(int i=head[u];i;i=e[i].next)
		{
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].val)
			{
				dis[v]=dis[u]+e[i].val;
				q.push(make_pair(dis[v],v));
			}
		}
	}
	return;
}
